The M(2m: hereinafter written as 2**m)-point radix 2 pipeline FFT is known as an arithmetic pipeline implemented in m stages each including data permutation and arithmetic operation modules. For more particulars, reference may have to be made to “THEORY AND APPLICATION OF DIGITAL SIGNAL PROCESSING” by Lawrence R. Rabiner, Bernard Gold, published by PRENTICE HALL, 1975, Article “Radix 2 Pipeline FFT”, p. 604.
In the case where the number of data undergoing Fourier transform (hereinafter also referred to as the transform point number) can be decomposed such that N=L×M, then L-point FFT operation is performed M times in accordance with the principle of the FFT, and after twiddle factor multiplication performed for N data obtained, M-point FFT (fast Fourier transform) operation is performed L times, whereby Fourier transform can be accomplished. There have been proposed several methods of implementing the pipelines by decomposing the N-point Fourier transform.
According to one of the methods, in the case where the transform point number N can be expressed as N=L×L, L-point parallel type Fourier transform circuit (whose inputs/outputs are equal to the transform point number L) is disposed in each of the preceding stage and the succeeding stage, wherein a data permutating circuit termed the corner turner is disposed in precedence to each of the L-point parallel type Fourier transform circuits for data supply thereto.
Further, in the case where the transform point number N is given by N=L×M (L=P×M, where P is an integer greater than one), similar arrangement may be adopted. In any case, width of parallelism (or parallelism width) is given by L.
Parenthetically, the corner turner is a circuit designed to output two-dimensional data after effecting the transposition thereof by regarding the two-dimensional data as a matrix (refer to Japanese Patent Application Laid-Open No. 59-087575).
In addition, according to another method, a number A of (2**m)-point radix 2 pipeline FFT circuits each having two-parallel input/outputs are disposed in parallel in the preceding stage in the case where the transform point number N is given by N=(2**m)×A, while in the succeeding stage, a pair of A-point parallel type Fourier transform circuits (having a pipeline width A) are disposed in parallel with each other. In that case, the overall parallelism width is given by 2×A.
In the Fourier transform apparatuses described above, with the structurization scheme that the parallel type Fourier transform circuits are disposed in the preceding stage and the succeeding stage, respectively, the input parallel point number or the pipeline width assumes a value greater than or equal to the square root of the Fourier transform point number, which means that the pipeline width smaller than the square root of the transform point number N can not be obtained, to a disadvantage (refer to Patent Publication No. 63-36553).
With another structurization scheme according to which a plurality of radix 2 pipeline FFT circuits each having two parallel input/outputs are disposed in parallel in the preceding stage with a pair of parallel type Fourier transform apparatus being disposed in the succeeding stage, the input parallel point number or the pipeline width can be determined with less dependency on the Fourier transform point number. However, since the input parallelism or the transform point number of the parallel type Fourier transform circuits in the succeeding stage is equal to the number A of the radix 2 pipeline FFTs each of two parallel input/outputs disposed in the preceding stage (i.e., a half of the pipeline width of the apparatus), implementation of the apparatus will encounter difficulty due to the spatial parallelity of the parallel type Fourier transform circuits in the succeeding stage, giving rise to a problem (refer to Japanese Patent Application Laid-Open No. 4-245562).
In the light of the state of art, it is an object of the present invention to provide a Fourier transform apparatus whose pipeline width has substantially no dependency on the transform point numbers of the individual pipeline FFT circuits in each stage.